%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Masters/Doctoral Thesis 
% LaTeX Template
% Version 1.41 (9/9/13)
%
% This template has been downloaded from:
% http://www.latextemplates.com
%
% Original authors:
% Steven Gunn 
% http://users.ecs.soton.ac.uk/srg/softwaretools/document/templates/
% and
% Sunil Patel
% http://www.sunilpatel.co.uk/thesis-template/
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
% Note:
% Make sure to edit document variables in the Thesis.cls file
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[11pt, a4paper, oneside]{Thesis} % Paper size, default font size and one-sided paper

\graphicspath{{Pictures/}} % Specifies the directory where pictures are stored
\usepackage{graphicx}
\usepackage{xfrac}
\usepackage{listings} 
\usepackage{pgfplots}
\usepackage{pgfplots, pgfplotstable}
\usepackage[square, numbers, comma, sort&compress]{natbib} % Use the natbib reference package - read up on this to edit the reference style; if you want text (e.g. Smith et al., 2012) for the in-text references (instead of numbers), remove 'numbers' 
\hypersetup{urlcolor=blue, colorlinks=true} % Colors hyperlinks in blue - change to black if annoying
\title{\ttitle} % Defines the thesis title - don't touch this

\begin{document}

\frontmatter % Use roman page numbering style (i, ii, iii, iv...) for the pre-content pages

\setstretch{1.3} % Line spacing of 1.3

% Define the page headers using the FancyHdr package and set up for one-sided printing
\fancyhead{} % Clears all page headers and footers
\rhead{\thepage} % Sets the right side header to show the page number
\lhead{} % Clears the left side page header

\pagestyle{fancy} % Finally, use the "fancy" page style to implement the FancyHdr headers

\newcommand{\HRule}{\rule{\linewidth}{0.5mm}} % New command to make the lines in the title page

% PDF meta-data
\hypersetup{pdftitle={\ttitle}}
\hypersetup{pdfsubject=\subjectname}
\hypersetup{pdfauthor=\authornames}
\hypersetup{pdfkeywords=\keywordnames}

%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\begin{titlepage}
\begin{center}

\textsc{\LARGE \univname}\\[1.5cm] % University name
\textsc{\Large Thesis}\\[0.5cm] % Thesis type

\HRule \\[0.2cm] % Horizontal line
{\huge \bfseries \ttitle}\\[0.2cm] % Thesis title
\HRule \\[0.5cm] % Horizontal line
 
\begin{minipage}{0.4\textwidth}
\begin{flushleft} \large
\emph{Author:}\\
{\authornames}\footnotemark
\\
\emph{\\Group Members:}\\
{Benjamin Hugo\\Heinrich Strauss}
\end{flushleft}
\end{minipage}
\begin{minipage}{0.4\textwidth}
\begin{flushright} \large
\emph{Supervisors:} \\
{\supname} % Supervisor name - remove the \href bracket to remove the link  
\end{flushright}
\end{minipage}\\[1cm]
 
\large \textit{A thesis submitted in fulfilment of the requirements\\ for the degree of \degreename}\\[0.3cm] % University requirement text
\textit{in the}\\[0.4cm]
\groupname\\\deptname\\[0.5cm] % Research group name and department name
 
{\large \today}\\ % Date
%\includegraphics{Logo} % University/department logo - uncomment to place it

\end{center}

\begin{center}
\begin{tabular}{|c|l|c|c|c|}
\hline
& \textbf{Category} & \textbf{Min} & \textbf{Max} & \textbf{Chosen} \\ \hline
1 & Requirement Analysis and Design & 0 & 20 & 10 \\ \hline
2 & Theoretical Analysis & 0 & 25 & 0 \\  \hline 
3 & Experimental Design and Evaluation & 0 & 20 & 5 \\ \hline 
4 & System Development and Implementation & 0 & 15 & 15 \\ \hline 
5 & Results, Findings and Conclusion & 10 & 20 & 15 \\ \hline 
6 & Aim Formulation and Background Work & 10 & 15 & 15 \\  \hline 
7 & Quality of Report Writing and Presentation & \multicolumn{2}{c|}{10} & 10 \\ \hline 
8 & Adherence to Project Proposal and Quality of Deliverables & \multicolumn{2}{c|}{10} & 10 \\ \hline 
9 & Overall General Project Evaluation & 0 & 10 & 0 \\ \hline 
\multicolumn{2}{|l|}{\textbf{Total marks}} & \multicolumn{2}{c|}{\textbf{80}} & \textbf{80} \\
\hline
\end{tabular}
\end{center}

\footnotetext{The financial assistance of the National Research Foundation (NRF) towards this research is hereby acknowledged. Opinions expressed and conclusions arrived at, are those of the author and are not necessarily to be attributed to the NRF}

\end{titlepage}

%----------------------------------------------------------------------------------------
%	DECLARATION PAGE
%	Your institution may give you a different text to place here
%----------------------------------------------------------------------------------------

%\Declaration{

%\addtocontents{toc}{\vspace{1em}} % Add a gap in the Contents, for aesthetics

%I, \authornames, declare that this thesis titled, '\ttitle' and the work presented in it are my own. I confirm that:

%\begin{itemize} 
%\item[\tiny{$\blacksquare$}] This work was done wholly or mainly while in candidature for a research degree at this University.
%\item[\tiny{$\blacksquare$}] Where any part of this thesis has previously been submitted for a degree or any other qualification at this University or any other institution, this has been clearly stated.
%\item[\tiny{$\blacksquare$}] Where I have consulted the published work of others, this is always clearly attributed.
%\item[\tiny{$\blacksquare$}] Where I have quoted from the work of others, the source is always given. With the exception of such quotations, this thesis is entirely my own work.
%\item[\tiny{$\blacksquare$}] I have acknowledged all main sources of help.
%\item[\tiny{$\blacksquare$}] Where the thesis is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed myself.\\
%\end{itemize}
 
%Signed:\\
%\rule[1em]{25em}{0.5pt} % This prints a line for the signature
 
%Date:\\
%\rule[1em]{25em}{0.5pt} % This prints a line to write the date
%}

%\clearpage % Start a new page

%----------------------------------------------------------------------------------------
%	QUOTATION PAGE
%----------------------------------------------------------------------------------------

%\pagestyle{empty} % No headers or footers for the following pages

%\null\vfill % Add some space to move the quote down the page a bit

%\textit{``Thanks to my solid academic training, today I can write hundreds of %words on virtually any topic without possessing a shred of information, which is %how I got a good job in journalism."}

%\begin{flushright}
%Dave Barry
%\end{flushright}

%\vfill\vfill\vfill\vfill\vfill\vfill\null % Add some space at the bottom to position the quote just right

%\clearpage % Start a new page

%----------------------------------------------------------------------------------------
%	ABSTRACT PAGE
%----------------------------------------------------------------------------------------

\addtotoc{Abstract} % Add the "Abstract" page entry to the Contents

\abstract{\addtocontents{toc}{\vspace{1em}} % Add a gap in the Contents, for aesthetics
Square Kilometer Array (SKA) is building a large radio telescopes array in South Africa which collects radio frequencies from objects in space. The radio frequency data is collected at 2 TB per second for many hours at a time, this means the final output file size lies in exabyte range. SKA have thus started plans to compress this data to alleviate huge expenses in storage and network speeds. The compression must not however negatively impact scan throughput, and so a Real Time compression scheme is required.
\\
\\
Since radio data is very noisy and many signals of interest are weak, it is desirable to retain all detail in the signal, which suggests using a lossless compression scheme. Since each scan ranges in the exabytes, but has few unique frequencies, an Entropy Encoding scheme seems to be the best approach for a chance of high compression ratios. There are 2 well known Entropy Encoding schemes, Arithmetic Coding which predominantly uses Dynamic Programming schemes and Huffman Coding which allows for many sections to be parallelised. Thus Huffman coding is the better candidate for the required SKA throughput.
\\
\\
The Huffman Coding algorithm we have designed for SKA uses GPUs and CPU parallelisation in order to achieve 71MB per second throughput on the tested system and a compression ratio of 41\%. Which is better than the standard compression tools such as BZIP2 in both throughput and compression ratio but does not achieve real time compression for the SKA data.   
}
\clearpage % Start a new page

%----------------------------------------------------------------------------------------
%	ACKNOWLEDGEMENTS
%----------------------------------------------------------------------------------------

\setstretch{1.3} % Reset the line-spacing to 1.3 for body text (if it has changed)

\acknowledgements{\addtocontents{toc}{\vspace{1em}} % Add a gap in the Contents, for aesthetics
I would to thank both my supervisors, A/Prof. James Gain and A/Prof. Patrick Marais, for their help throughout the project. Their insights truly did help me through the main processes and the final report of the project and are greatly appreciated.
\\
\\
I would then like to thank Jason Mannley who works at the SKA for all his help in the understanding of the SKA pipeline, and access to some SKA data.
\\
\\
Finally I would like to thank my project team member Benjamin Hugo who helped me work through sections code in order to find bugs or speed up certain processes.
}
\clearpage % Start a new page

%----------------------------------------------------------------------------------------
%	LIST OF CONTENTS/FIGURES/TABLES PAGES
%----------------------------------------------------------------------------------------

\pagestyle{fancy} % The page style headers have been "empty" all this time, now use the "fancy" headers as defined before to bring them back

\lhead{\emph{Contents}} % Set the left side page header to "Contents"
\tableofcontents % Write out the Table of Contents

\lhead{\emph{List of Figures}} % Set the left side page header to "List of Figures"
\listoffigures % Write out the List of Figures

%\lhead{\emph{List of Tables}} % Set the left side page header to "List of Tables"
%\listoftables % Write out the List of Tables

%----------------------------------------------------------------------------------------
%	ABBREVIATIONS
%----------------------------------------------------------------------------------------

\clearpage % Start a new page

\setstretch{1.5} % Set the line spacing to 1.5, this makes the following tables easier to read

\lhead{\emph{Abbreviations}} % Set the left side page header to "Abbreviations"
\listofsymbols{ll} % Include a list of Abbreviations (a table of two columns)
{
\textbf{SKA} & \textbf{S}quare \textbf{K}ilometer \textbf{A}rray \\
\textbf{CPU} & \textbf{C}entral \textbf{P}rocessing \textbf{U}nit \\
\textbf{GPU} & \textbf{G}raphical \textbf{P}rocessing \textbf{U}nit \\
\textbf{RLE} & \textbf{R}un \textbf{L}ength \textbf{E}ncoding \\
\textbf{AHC} & \textbf{A}daptive \textbf{H}uffman \textbf{C}oding \\
\textbf{SIMD} & \textbf{S}ingle \textbf{I}nstruction \textbf{M}ultiple \textbf{D}ata \\
\textbf{LZ} & \textbf{L}empel \textbf{Z}iv \\
\textbf{RAM} & \textbf{R}andom \textbf{A}ccess \textbf{M}emory \\
\textbf{SM/SMX} & \textbf{S}treaming \textbf{M}ultiprocessor - the X is used for Kepler series SMs \\
\textbf{CUDA} & \textbf{C}ompute \textbf{U}unified \textbf{D}evice \textbf{A}rchitecture \\
\textbf{STL} & \textbf{S}tandard \textbf{T}emplate \textbf{L}ibrary \\
\textbf{FPGA} & \textbf{F}ield \textbf{P}rogrammable \textbf{G}ate \textbf{A}rray \\
\textbf{Mb} & \textbf{M}ega\textbf{b}it \\
\textbf{Gb} & \textbf{G}iga\textbf{b}it \\
\textbf{MB} & \textbf{M}ega\textbf{B}yte \\
\textbf{GB} & \textbf{G}iga\textbf{B}yte \\
\textbf{TB} & \textbf{T}era\textbf{B}yte \\

%\textbf{Acronym} & \textbf{W}hat (it) \textbf{S}tands \textbf{F}or \\
}

%----------------------------------------------------------------------------------------
%	PHYSICAL CONSTANTS/OTHER DEFINITIONS
%----------------------------------------------------------------------------------------

%\clearpage % Start a new page

%\lhead{\emph{Physical Constants}} % Set the left side page header to "Physical Constants"

%\listofconstants{lrcl} % Include a list of Physical Constants (a four column table)
%{
%Speed of Light & $c$ & $=$ & $2.997\ 924\ 58\times10^{8}\ \mbox{ms}^{-\mbox{s}}$ %(exact)\\
% Constant Name & Symbol & = & Constant Value (with units) \\
%}

%----------------------------------------------------------------------------------------
%	SYMBOLS
%----------------------------------------------------------------------------------------

%\clearpage % Start a new page

%\lhead{\emph{Symbols}} % Set the left side page header to "Symbols"

%\listofnomenclature{lll} % Include a list of Symbols (a three column table)
%{
%$a$ & distance & m \\
%$P$ & power & W (Js$^{-1}$) \\
% Symbol & Name & Unit \\

%& & \\ % Gap to separate the Roman symbols from the Greek

%$\omega$ & angular frequency & rads$^{-1}$ \\
% Symbol & Name & Unit \\
%}

%----------------------------------------------------------------------------------------
%	DEDICATION
%----------------------------------------------------------------------------------------

\setstretch{1.3} % Return the line spacing back to 1.3

\pagestyle{empty} % Page style needs to be empty for this page

%\dedicatory{For/Dedicated to/To my\ldots} % Dedication text

\addtocontents{toc}{\vspace{2em}} % Add a gap in the Contents, for aesthetics

%----------------------------------------------------------------------------------------
%	THESIS CONTENT - CHAPTERS
%----------------------------------------------------------------------------------------

\mainmatter % Begin numeric (1,2,3...) page numbering

\pagestyle{fancy} % Return the page headers back to the "fancy" style

% Include the chapters of the thesis as separate files from the Chapters folder
% Uncomment the lines as you write the chapters

\input{Chapters/introduction}
\input{Chapters/Background}
\input{Chapters/Design}
\input{Chapters/AHCImplementation}
\input{Chapters/HCImplementation}
\input{Chapters/Results}
\input{Chapters/Discussion}

%----------------------------------------------------------------------------------------
%	THESIS CONTENT - APPENDICES
%----------------------------------------------------------------------------------------

\addtocontents{toc}{\vspace{2em}} % Add a gap in the Contents, for aesthetics

\appendix % Cue to tell LaTeX that the following 'chapters' are Appendices

% Include the appendices of the thesis as separate files from the Appendices folder
% Uncomment the lines as you write the Appendices

%\input{Appendices/AppendixA}
%\input{Appendices/AppendixB}
%\input{Appendices/AppendixC}

\addtocontents{toc}{\vspace{2em}} % Add a gap in the Contents, for aesthetics

\backmatter

%----------------------------------------------------------------------------------------
%	BIBLIOGRAPHY
%----------------------------------------------------------------------------------------

\label{Bibliography}

\lhead{\emph{Bibliography}} % Change the page header to say "Bibliography"

\bibliographystyle{unsrtnat} % Use the "unsrtnat" BibTeX style for formatting the Bibliography

\bibliography{Bibliography} % The references (bibliography) information are stored in the file named "Bibliography.bib"

\end{document}  